/**
 * Created with IntelliJ IDEA.
 * Description :
 * User: $ {USER}
 * Date: $ {YEAR}-$ {MONTH}一$ { DAY}
 * Time: ${ TIME}
 */

/**
 *  题目：重排链表
 *  思路：找到链表的中间节点，将中间节点之后的节点给反转，接着把反转的链表给按照题目的意思给串起来
 */
public class Test {
    public static void main(String[] args) {
        ListNode head5 = new ListNode(5);
        ListNode head4 = new ListNode(4, head5);
        ListNode head3 = new ListNode(3, head4);
        ListNode head2 = new ListNode(2, head3);
        ListNode head = new ListNode(1, head2);
        reorderList(head);
    }
    public static void reorderList(ListNode head) {
        // 找到链表的中间节点（断开），从这里开始反转链表，将反转后的与前面交错链接在一起
        ListNode mid = findMidListNode(head);
        ListNode newHead = reverseLinkedList(mid);
        // 如果这里写的newHead，那么会导致死循环（尾节点指向自己）
        // 因为到最后head.next一定会指向newHead链表尾节点
        // 如果我们newHead走到尾节点了，那么交错链表一定有雏形了
        while (newHead.next != null) {
            ListNode headNext = head.next;
            ListNode newHeadNext = newHead.next;
            head.next = newHead;
            newHead.next = headNext;
            head = headNext;
            newHead = newHeadNext;
        }
    }

    // 找到链表的中间节点（快慢指针）
    public static ListNode findMidListNode (ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    // 反转链表
    public static ListNode reverseLinkedList (ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 注意：这里得采用标准的完全反转，否则会导致在后面交错链接时出现死循环的现象
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return prev;
    }
}


class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
